Minimum range query using segment trees/SegmentTreeTester.cpp

   1 #include "SegmentTree.cpp"
   2
   3 #include <cstdlib>
   4 #include <cstdio>
   5 #include <cassert>
   6
   7 SegmentTree t;
   8
   9 void build_random_tree(int n = 100){
  10   t.arr.resize(n);
  11   for (int i=0; i<n; ++i) t.arr[i] = random() * (random() % 2 ? -1 : 1);
  12   t.initialize();
  13 }
  14
  15 void check_query_correctness(int u, int v){
  16   assert(u <= v);
  17   int index = u;
  18   for (int k=u; k<=v; ++k) if (t.arr[k] < t.arr[index]) index = k;
  19   int q = t.query(u, v);
  20   printf("Range [%d, %d]:\n", u, v);
  21   printf("     Tree query: index = %d, element = %d\n", q, t.arr[q]);
  22   printf("   Lineal query: index = %d, element = %d\n", index, t.arr[index]);
  23   assert(index == q);
  24   printf("      SUCCESS\n");
  25 }
  26
  27 void check_random_queries(int times = 100){
  28   while (times--){
  29     int u = random() % t.n, v = random() % t.n;
  30     if (v < u) swap(u, v);
  31     check_query_correctness(u, v);
  32   }
  33 }
  34
  35 void check_update_correctness(int where, int what){
  36   vector<int> old = t.arr;
  37   t.update(where, what);
  38
  39   old[where] = what;
  40   printf("Update [%d] = %d\n", where, what);
  41   assert(t.arr == old);
  42   printf("      SUCCESS\n");
  43 }
  44
  45 void check_random_updates(int times = 100){
  46   while (times--){
  47     int where = random() % t.n, what = random() * (random() % 2 ? -1 : 1);
  48     check_update_correctness(where, what);
  49     //after an update, check some random queries to see if everyting remains fine.
  50     check_random_queries();
  51   }
  52 }
  53
  54 void print_array(const vector<int> &arr){
  55   for (int i=0; i<arr.size(); ++i) printf("%d ", arr[i]);
  56   printf("\n");
  57 }
  58
  59 int main(){
  60   int n = 10;
  61   build_random_tree(n);
  62   check_random_queries(2*n);
  63   check_random_updates();
  64   return 0;
  65 }